\subsection{存活性和中和}\label{sec:vote_stuck}

不论中心化与否，分布式共识的主要挑战是：在系统对它的一致性认可之前，一个陈述可能卡在某个长期不确定的状态中。因此，一个协议不会尝试直接去批准外部表现的值\todo{语句不通}。一旦``{\slot}$i$处的值是$x$''这一陈述被阻塞了，系统将会永久性的地不能够在{\slot}$i$处达成一致，从而失去存活性。解决方案是仔细地巧妙修改投票中的陈述。在我们真正关心的问题上(即关于{\slot}内容)切断一个被阻塞陈述必然是可能的。我们称废弃一个被阻塞的陈述的过程为\textit{中和}。

\begin{figure}
\centering
\begin{tikzpicture}[thick,
    node/.style={draw,ellipse,inner xsep=-1.5mm,align=center,text width=2cm,
      inner ysep=0pt,
      text depth=1ex,text height=1em,fewshade=\maincolor},
    transition/.style={->,very thick, shorten <=-3pt, shorten >=0pt,
      align=center,font={\small\openup-.5\jot},draw=few-gray}
  ]
\node[node] (B) at (-2.5,0) {二价的};
\node[node] (AV) at (1.5,1.5) {$a$-价的};
\node[node] (NAV) at (1.5,-1.5) {$\na$-价的};
\node[node] (stuck) at (5.5,0) {被阻塞};
\node[node] (AA) at (5.5,1.5) {$a$~被同意};
\node[node] (NAA) at (5.5,-1.5) {$\na$~被同意};
\coordinate (merge) at ([xshift=-1cm] stuck.west);
\begin{scope}[on background layer]
\draw[transition] (B) to[out=90,in=180,looseness=.9] (AV);
\draw[transition] (B) to[out=270,in=180,looseness=.9] (NAV);
%\draw[transition] (AV) to[out=-2,in=90,looseness=.9] (stuck);
%\draw[transition] (NAV) to[out=2,in=-90,looseness=.9] (stuck);
\draw[transition] (AV) -- (AA);
\draw[transition] (NAV) -- (NAA);
\draw[transition] (AV) to[out=-60,in=180] (merge) -- (stuck);
\draw[transition,-] (NAV) to[out=60,in=180] (merge);
\draw[transition,-] (B) to (merge);
\end{scope}
\end{tikzpicture}
\caption{陈述$a$在系统范围内可能的状态}
\label{fig:system-states}
\end{figure}

更具体地将，{图\ref{fig:system-states}}描述了一个系统范围内一个陈述$a$潜在可能的状态。最初，系统是\textit{二价的}。我们用它来说明：存在一个可能的事件序列，所有的完好节点会接受$a$；而存在另一个序列，所有的完好节点会\textit{拒绝}$a$(即接受和$a$相冲突的陈述$\bar a$)。在某些时刻，两种输出的其中一个可能会不再可能。如果没有完好节点可以拒绝$a$，我们称它是$a-\!\!$价的；反之，如果没有节点可以接受$a$，我们称它是$\bar a-\!\!$价的。

在一个FBAS系统从二价态转化成$a-\!\!$价时，存在一种可能的结果：所有的完好节点都接受了$a$。然而这种情形并不总是成立。考虑像PBFT这样的四节点系统$\left\{v_1,\ldots,v_4\right\}$，其中任意三个节点构成了一个{\quorum}。如果$v_1$和$v_2$赞成$a$，系统变成了$a-\!\!$价的；没有哪三个节点可以批准一个相冲突的陈述。然而，如果$v_3$和$v_4$最终投票赞成了和$a$冲突的$\bar a$，它也不可能批准$a$。在这种情形，$a$的状态是永远不确定的，或称之为\textit{被卡住的}。

\begin{figure}
\centering 
\tabulinesep2pt
\begin{tabu} to .85\textwidth{ll}\toprule
\rowfont\bfseries 局部状态 & $a$系统范围的状态\\
\midrule
未提交 & 未知 (对任何节点) \\
已赞成~$a$ & 未知(对任何节点) \\
已赞成~$\na$ & 未知(对任何节点) \\
已接受~$a$ & 被阻塞, $a$-价的, or $a$ 被同意 \\
已确认~$a$ & $a$ 被同意 \\
\bottomrule
\end{tabu}
\caption{对于陈述$a$的状态一个完好节点所知道的信息}
\label{fig:localglobal}
\end{figure}

正如在{图\ref{fig:unresolvable}a}中所看到的那样，甚至一旦一个完好节点接受$a$，系统可能还是会在达到系统范围内对$a$的认可上失败。然而，根据定理\ref{thm:confirmed_stats_keep_liveness}，一旦一个完好节点确认$a$，所有的完好节点最终都会接受它；因此系统对$a$认可。{图\ref{fig:localglobal}}总结了完好节点从它们自己关于一个陈述的局部状态可知的全局状态。

为了保持共识的可能性，一个协议必须确保每个陈述是不可辩驳因而不会被卡住，或者是可中和的因而如果被卡住不会阻塞进展。有两种流行的处理可中和陈述的方法：\textit{基于视图}的方法，由\textit{视图采样副本}~\cite{Oki:1988:VRN:62546.62549}最先提出并得到PBFT系统~\cite{Castro:1999:PBFT}的青睐；\textit{基于表决}的方法，由\textit{Paxos}~\cite{Lamport:1998:PP:279227.279229}发明。基于表决的方法可能更难以理解~\cite{Ongaro:2014:SUC:2643634.2643666}。更为混乱的是，人们经常称基于视图复制的方法为``Paxos算法''或者断言两种算法是相同的而事实上它们不是~\cite{6894199}。

基于视图的协议将投票中的{\slot}和单调递增的视图数联系相关联。万一在视图$n$处共识卡在了第$i$个{\slot}上，节点通过认可视图$n$包含少于$i$个有意义的{\slot}并且转向一个大一点的视图数。基于表决的方法将投票中的\textit{值}和单调递增的表决数相关联。万一一个表决被卡住了，节点用一个更大的表决数重新尝试，仔细选择和之前任何的不确定表决相冲突的值。

本文的工作采用了基于表决的方法，因为这样做更加简化了消除显著的基础节点(或称领导节点)的过程。例如存在赶上领导节点的行为~\cite{Lamport:2011:BPR:2075029.2075058}的可能。
